package com.power.algorithm;

public class Solution21 {
    ListNode ln1;
    ListNode ln2;
    ListNode newHead;
    ListNode tail;

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //递归合并
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //两条线路不为空就依次遍历合并
       if(l1 ==null){
           return l2;
       }else if(l2 ==null){
           return l1;
       }else if(l1.val >= l2.val){
           l2.next = mergeTwoLists(l2.next,l1);
       }else if (l1.val < l2.val){
           l1.next = mergeTwoLists(l1.next,l2);
       }
        return newHead;
    }

    public static void main(String[] args) {
        Solution21 solution21 = new Solution21();
        for (int i = 0; i < 10; i++) {
            if (i % 2 == 0) {
                solution21.addLn1(i);
            } else {
                solution21.addLn2(i);
            }
        }
        solution21.display(solution21.ln1);
        solution21.display(solution21.ln2);

        solution21.mergeTwoLists(solution21.ln1, solution21.ln2);

    }

    public void display(ListNode listNode) {
        if (listNode == null) {
            return;
        }
        while (listNode != null) {
            System.out.print(" " + listNode.val);
            if (listNode.next != null) {
                listNode = listNode.next;
            } else {
                System.out.println("\n");
                return;
            }
        }
        System.out.println("\n");
    }

    public void addLn1(int val) {
        ListNode newNode = new ListNode(val);
        if (ln1 == null) {
            ln1 = newNode;
        } else {
            ListNode tmp = ln1;
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = newNode;
        }
    }

    public void addLn2(int val) {
        ListNode newNode = new ListNode(val);
        if (ln2 == null) {
            ln2 = newNode;
        } else {
            ListNode tmp = ln2;
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = newNode;
        }
    }
}
